package com.yitiao.data_algorithms.leetcode.editor.cn;

import com.yitiao.data_algorithms.leetcode.editor.cn.base.ListNode;
import com.yitiao.data_algorithms.leetcode.editor.cn.base.TreeNode;

class TwoSumIiInputArrayIsSorted {
    // 2022-08-20 15:16:11
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[] twoSum(int[] numbers, int target) {
            int[] ans = new int[2];
            // 如何更快的寻找第二个数
            for (int i = 0; i < numbers.length; i++) {
                int first = numbers[i];
                int left = i + 1;     // 左端点
                int right = numbers.length - 1; // 右
                while (left <= right) {
                    int mid = (right - left) / 2 + left;
                    if (numbers[mid] + first == target) {
                        ans[0] = i + 1;
                        ans[1] = mid + 1;
                        return ans;
                    } else if (numbers[mid] + first > target) {
                        // 修改端点
                        right = mid - 1;
                    } else {
                        left = mid + 1;
                    }
                }
            }
            return ans;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}